百面 优化算法
机器学习算法=模型表征+模型评估+优化算法
优化算法所做的事情就是在模型表征空间中找到模型评估指标最好的模型。
经典的支持向量机对应的模型表征和评估指标分别为线性分类模型和最大间隔，逻辑回归对应的模型表征和评估指标则分别为线性分类模型和交叉熵。
有监督学习的损失函数
问：有监督学习涉及的损失函数有哪些？请列举并简述它们的特点。
答：在有监督学习中，损失函数刻画了模型和训练样本的匹配程度。
对于二分类问题，最自然地损失函数是0-1损失。
其中1p是指示函数，当且仅当p为真时取值为1，否则取值为0。该损失函数能够直观地刻画分类的错误率，但是由于其非凸非光滑的特点，使得算法很难直接对其进行优化。
0-1损失的一个代理损失函数是hinge损失函数。
hinge损失函数是0-1损失函数相对紧的凸上界，且当fy>=1时，该函数不对其做任何惩罚。hinge损失在fy=1处不可导，因此不能用梯度下降法进行优化，而是用次梯度下降法。
0-1损失的另一个代理损失函数是logistic损失函数：
logistic损失函数也是0-1损失函数的凸上界，且该函数处处光滑，因此可以用梯度下降法进行优化。但是，该损失函数对所有样本点都有所惩罚，因此对异常值相对更敏感一些。
当预测值f属于[-1,1]时，另一个代理损失函数就是交叉熵损失函数。
交叉熵损失函数也是0-1损失函数的光滑凸上界。
对于回归问题，最常用的损失函数是平方损失函数。
平方损失函数是光滑函数，能够用梯度下降法进行优化。当预测值距离真实值越远时，平方损失函数的惩罚力度越大，因为它对异常点比较敏感。可以采用绝对损失函数来解决这个问题。
绝对损失对异常点更鲁棒一些，但是绝对损失函数在f=y处无法求导数。综合考虑可导性和对异常点的鲁棒性，可以采用huber损失函数。
huber损失函数在|f-y|较小时为平方损失，在|f-y|较大时为线性损失，处处可导，且对异常点鲁棒。
机器学习中的优化问题
问： 机器学习中优化问题，哪些是凸优化问题，哪些是非凸优化问题？
答：凸函数，函数L是凸函数当且仅当对定义域中的任意两点x，y和任意实数λ∈[0,1]总有
逻辑回归对应的就是凸优化问题，对于二分类问题，Y={1,-1},假设模型参数为θ，则逻辑回归的优化问题为。
可以通过计算目标函数的二阶Hessian矩阵来验证凸性。令
对该函数求一阶导，得到：
继续求导，得到函数的Hessian矩阵
该矩阵满足半正定的性质。
因此
函数L为凸函数。对于凸优化问题，所有的局部极小值都是全局极小值，因此这类问题一般认为是比较容易求解的问题。
主成分分析的优化问题为非凸优化问题。一般来说，非凸优化问题被认为是比较南求解的问题，但主成分分析是一个特例，我们可以借助SVD直接得到主成分分析的全局极小值。
总结与扩展：其他凸优化的例子包括支持向量机，线性回归等线性模型，非凸优化问题的例子包括低秩模型(如矩阵分解),深度神经网络模型。
经典优化算法
问题：无约束优化问题的优化方法有哪些？对于无约束优化问题：
其中目标函数L是光滑的，求解该问题的优化算法有哪些，适用场景是什么。
答：优化算法分为直接法和迭代法。
直接法，就是能够直接给出优化问题的最优解。直接法不是万能的。直接法要求目标函数需要满足两个条件，第一个是，L是凸函数。二，若L是凸函数，那么θ是最优解的充分必要条件是L在θ处的梯度为0。
即
经典的例子是岭回归，其最优解为：
直接法要满足的这两个条件限制了它的应用范围。因此，在很多实际问题中，会采用迭代法。迭代法就是迭代地修正对最优解得估计。迭代法又分为一阶法和二阶法两类。
一阶法的迭代公式为：
其中α称为学习率，一阶法也称为梯度下降法，梯度就是目标函数的一阶信息。
二阶法的迭代公式
二阶法也称为牛顿法，Hessian矩阵就是目标函数的二阶信息，二阶法的收敛速度一般要远快于一阶法，但是在高维情况下，Hessian矩阵求逆的计算复杂度很大，而且当目标函数非凸时，二阶法有可能会收敛到鞍点。
梯度验证
在实际应用中，写出计算梯度的代码后，通常需要验证自己写的代码是否正确。
问：如何验证求目标函数梯度功能的正确性？
答：ei是单位向量，维度与θ相同，仅在第i个位置取值为1，其余位置取值为0。可以取h为一个比较小的数(例如10的-7次方)，则有
在实际应用中，随机初始化θ，取h为较小的数(例如10的-7次方)，并对i=1,2,…,n,依次验证
是否成立。如果对于某个下标i，该不等式不成立，则有以下两种可能。
1 该下标对应的M过大
2 该梯度分量计算不正确
此时可以固定θ，减小h为原来的十分之一，并再次计算下标i对应的近似误差，若近似误差越减小为原来的百分之一，则对应第一种可能，我们应该采用更小的h重新做一次梯度验证，否则对应第二种可能，应检查梯度的代码是否有错误。
随机梯度下降法
问：当训练数据量特别大时，经典的梯度下降法存在什么问题，需要做如何改进？
答：经典的梯度下降法在每次对模型参数进行更新时，需要遍历所有的训练数据。当M很大时，这需要很大的计算量，耗费很长的计算时间，在实际应用中基本不可行。为了解决该问题，随机梯度下降法(SGD)用单个训练样本的损失来近似平均损失，即随机梯度下降法用单个训练数据即可对模型参数进行一次更新，大大加快了收敛速率。该方法也非常适用于数据源源不断到来的在线更新场景。
为了降低随机梯度的方差，从而使得迭代算法更加稳定，也为了充分利用高度优化的矩阵运算操作，在实际应用中我们会同时处理若干训练数据，该方法被称为小批量梯度下降法(Mini-Batch Gradient Descent)
有三个需要注意的地方：
1.选取参数m，在不同的应用中，最优的m通常会不一样，需要通过调参选取。一般m取2的幂次能充分利用矩阵运算操作，所以可以在2的幂次中挑选出最优的取值，例如32，64，128，256等。
2.挑选m个训练数据，为了避免数据的特定顺序给算法收敛带来的影响，一般会在每次遍历训练数据之前，先对所有的数据进行随机排序，然后在每次迭代时按顺序挑选m个训练数据直至遍历完所有的数据。
3.选取学习速率α，为了加快收敛速率，同时提高求解精度，通常会采用衰减学习速率的方案:一开始算法采用较大的学习速率，当误差曲线进入平台期后，减小学习速率做更精细的调整。最优的学习速率方案也通常需要调参才能得到。
综上，通常采用小批量梯度下降法解决训练数据量过大的问题。每次更新模型参数时，只需要处理m个训练数据即可，其中m是一个远小于总数据量M的常数，这样能够大大加快训练过程。
随机梯度下降法的加速
提到深度学习中的优化方法，人们通常会想到随机梯度下降法。但是，随机梯度下降法并不是万金油，有时候反而会成为一个坑。当设计出一个深度神经网络时，如果只知道用随机梯度下降法来训练模型，那么当得到一个比较差的训练结果时，可能会放弃在这个模型上继续投入精力。然而，造成训练效果差的真正原因，可能并不是模型的问题，而是随机梯度下降法在优化过程中失效了，这可能会导致你丧失一次新发现的机会。
问：随机梯度下降法偶尔也会失效，无法给出满意的训练结果，这是为什么？
答：随机梯度下降法放弃了对梯度准确性的追求，每步仅仅随机采样一个或少量样本来估计当前梯度，计算速度快，内存开销小。但由于每步接受的信息量有限，随机梯度下降法对梯度的估计常常出现偏差，造成目标函数曲线收敛得很不稳定，伴有剧烈波动，有时甚至出现不收敛的情况。
深度学习中的优化问题本身就很难，有太多局部最优点的陷阱。这些陷阱对随机梯度下降法和批量梯度下降法都是普遍存在的。但对随机梯度下降法来说，可怕的不是局部最优点，而是山谷和鞍点两类地形。
山谷顾名思义就是狭长的山间小道，左右两边是峭璧;鞍点的形状像是一个马鞍，一个方向上两头翘，另一个方向上两头垂，而中心区域是一片近乎水平的平地。
山谷地形
在山谷中，准确的梯度方向是沿山道向下，稍有偏离就会撞向山壁，而粗糙的梯度估计使得它在两山壁间来回反弹震荡，不能沿山道方向迅速下降，导致收敛不稳定和收敛速度慢。在鞍点处，随机梯度下降法会走入一片平坦之地，结果就停滞下来。
问：解决之道—惯性保持和环境感知。
答：1.动量(Momentum)方法。
随机梯度下降法更新公式为：
动量方法模型参数迭代公式为：
具体来说，前进步伐-v,由两部分组成。一是学习速率乘以当前估计的梯度g;二是带衰减的前一次步伐v。这里，惯性就体现在对前一次步伐信息的重利用上。类比中学物理知识，当前梯度就好比当前时刻受力产生的加速度，前一次步伐好比前一时刻的速度，当前步伐好比当前时刻的速度。为了计算当前时刻的速度，应当考虑前一时刻速度和当前加速度共同作用的结果，因此vt直接依赖于vt-1 和gt, 而不仅仅是gt。另外，衰减系数y扮演了阻力的作用。
AdaGrad方法
随机梯度下降法对环境的感知是指在参数空间中，根据不同参数的一些经验性判断，自适应地确定参数的学习速率，不同参数的更新步幅是不同的。例如，在文本处理中训练词嵌入模型的参数时，有的词或词组频繁出现，有的词或词组则极少出现。数据的稀疏性导致相应参数的梯度的稀疏性，不频繁出现的词或词组的参数的梯度在大多数情况下为零，从而这些参数被更新的频率很低。在应用中，我们希望更新频率低的参数可以拥有较大的更新步幅，而更新频率高的参数的步幅可以减小。AdaGrad方法采用“历史梯度平方和”来衡量不同参数的梯度的稀疏性，取值越小表明越稀疏，具体的更新公式表示为
分母求和的形式实现了退火过程，这是很多优化技术中常见的策略，意味着随着时间推移，学习速率越来越小，从而保证了算法的最终收敛。
Adam方法
Adam方法将惯性保持和环境感知这两个优点集于一身。一方面，Adam记录梯度的一阶矩(first moment) ，即过往梯度与当前梯度的平均，这体现了惯性保持;另一方面，Adam还记录梯度的二阶矩(second moment)，即过往梯度平方与当前梯度平方的平均，这类似AdaGrad方法，体现了环境感知能力，为不同参数产生自适应的学习速率。
一阶矩和二阶矩采用类似于滑动窗口内求平均的思想进行融合，即当前梯度和近一段时间内梯度的平均值，时间久远的梯度对当前平均值的贡献呈指数衰减。具体来说，一阶矩和二阶矩采用指数衰退平均(exponentialdecay average)技术，计算公式
其中β，β2为衰减系数，m是一阶矩，v是二阶矩。
一阶矩相当于估计E[g]:由于当下梯度g,是随机采样得到的估计结果，因此更关注它在统计意义上的期望;二阶矩相当于估计E[g2]，这点与AdaGrad方法不同，不是g2从开始到现在的加和，而是它的期望。它们的物理意义是，当|m|大且v大时， 梯度大且稳定，这表明遇到一个明显的大坡，前进方向明确;当|m|趋于零 且v,大时，梯度不稳定，表明可能遇到一个峡谷，容易引起反弹震荡;当lm|大 且v,趋于零时，这种情况不可能出现;当|m|趋于零且v趋于零时，梯度趋于零，可能到达局部最低点，也可能走到一片坡度极缓的平地，此时要避免陷入平原(plateau) 。另外，Adam方法还考虑了m， v,在零初始值情况下的偏置矫正。具体来说，Adam的更新公式为
其中
L1正则化与稀疏性
问：L1正则化使得模型参数具有稀疏性的原理是什么？
角度1：解空间形状。
在二维的情况下，黄色的部分是L2和L1正则项约束后的解空间，绿色的等高线是凸优化问题中目标函数的等高线。由图可知，L2正则项约束后的解空间是圆形，而L1正则项约束的解空间是多边形。显然，多边形的解空间更容易在尖角处与等高线碰撞出稀疏解。
事实上，带正则项和带约束条件是等价的。为了约束w的可能取值空间从而防止过拟合，我们为该最优化问题加上一个约束，就是w的L2范数的平方不能大于m:
为了求解带约束条件的凸优化问题，写出拉格朗日函数。
若w 和λ 分别是原问题和对偶问题的最优解，根据KKT条件，它们应满足
L2正则化相当于为参数定义了一个圆形的解空间(因为必须保证L2范数不能大于m),而L1正则化相当于为参数定义了个棱形的解空间。如果原问题目标函数的最优解不是恰好落在解空间内,那么约束条件下的最优解一定是在解空间的边界上,而L1“棱角分明”的解空间显然更容易与目标函数等高线在角点碰撞,从而产生稀疏解。
L2的切点只有一个点，L1的话，一个尖尖可以和无数个圆连着。
角度2：函数叠加
棕线是原始目标函数L(w)的曲线图，最小值点在蓝点处，且对应w * 值非0。
考虑加上L2正则化项，目标函数变成L(w)+Cw2,其函数曲线为黄色。此时，最小值点在黄点处，对应w * 的绝对值减小了，但仍然非0.
考虑加上L1正则化项，目标函数变成L(w)+C|w|,其函数曲线为绿色，最小值点在红色处，对应的w是0，产生了稀疏性。
原因很直观，加入L1正则化后，对带正则项的目标函数求导，正则项部分产生的导数在原点左边部分是-C，在原点右边部分是C，因此，只要原目标函数的导数绝对值小于C，那么带正则项的目标函数在原点左边部分始终是递减的，在原点右边部分始终是递增的，最小值点自然在原点处。相反，L2正则项在原点处的导数是0，只要原目标函数在原点处的导数不为0，那么最小值点就不会在原点，所以L2只有减小w绝对值的作用，对解空间的稀疏性没有贡献。
在一些在线梯度下降算法中，往往会采用截断梯度法来产生稀疏性，这同L1正则项产生稀疏性的原理是类似的。
由上可以看出，L1产生稀疏性的概率比L2大很多，L2只有原目标函数导数为0这一种情况，L1则是原目标函数的导数绝对值小于C即可。
角度3：贝叶斯先验
从贝叶斯的角度来理解L1正则化和L2正则化，简单的解释是，L1正则化相当于对模型参数w引入了拉普拉斯先验，L2正 则化相当于引入了高斯先验，而拉普拉斯先验使参数为0的可能性更大。